package com.sx.sx1.lintcode.day717;

import java.util.*;

public class LC374 {

    static class Solution {
        /**
         * @param matrix: a matrix of m x n elements
         * @return: an integer list
         */
        public List<Integer> spiralOrder(int[][] matrix) {
            //模拟
            List<Integer> ans = new ArrayList<>();
            if(matrix.length ==0) return ans;
            int rows = matrix.length;
            int cols = matrix[0].length;
            int total = rows*cols;
            int idx=0,cutrows=0,cutcols=0,row=0,col=0;

            while (idx< total){
                if(idx>0) { //处理完一圈了
                    rows-=1;cols-=1;cutrows+=1;cutcols+=1;
                }

                //处理每一圈的上边
                while (idx<total && col < cols ) {
                    ans.add(matrix[row][col++]);
                    idx++;
                }
                row++;
                col-=1;

                //处理每一圈的右边
                while (idx<total && row<rows){
                    ans.add(matrix[row++][col]);
                    idx++;
                }

                row--;
                col--;

                //处理每一圈的下边
                while (idx<total && col>=cutcols){
                    ans.add(matrix[row][col--]);
                    idx++;
                }

                row-=1;
                col+=1;

                //处理每一圈的左边
                while (idx<total && row>cutrows){
                    ans.add(matrix[row--][col]);
                    idx++;
                }
                row+=1;
                col+=1;
            }
            return ans;
        }
    }

    public static void main(String[] args) {
        Solution obj = new Solution();
        System.out.println(obj.spiralOrder(new int[][]{
                {1,2,3},
                {4,5,6},
                {7,8,9}}));  // 1 2 3 6 9 8 7 4 5
        System.out.println(obj.spiralOrder(new int[][]{
                {6,4,1},
                {7,8,9}})); //6 4 1 9 8 7
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有199条未读消息，请及时查看
374 · 螺旋矩阵
算法
中等
通过率
32%

题目
题解54
笔记
讨论99+
排名
记录
描述
给定一个包含 m x n 个要素的矩阵，（m 行, n 列），按照螺旋顺序，返回该矩阵中的所有要素。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


样例
样例 1:

输入:[[ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ]]
输出: [1,2,3,6,9,8,7,4,5]
样例 2

输入:[[ 6,4,1 ], [ 7,8,9 ]]
输出: [6,4,1,9,8,7]
相关知识
学习《2024年3月北美大厂最新面试真题精讲》课程中的2.7Meta：最新面试精选004相关内容 ，了解更多相关知识！
标签
企业
Google
Facebook
Microsoft
Uber
相关题目

185
矩阵的之字型遍历
简单

381
螺旋矩阵 II
中等
推荐课程

ACM金牌逐行带刷班
最适合懒人的刷题课--躺平看算法大神在线coding，讲解思路+现场debug，手撕面试高频题
355/1856
已开启智能提示
发起考试
30 分 00 秒
123456789

控制台
        历史提交

 */